Search results for "Hash table"
showing 10 items of 13 documents
WarpDrive: Massively Parallel Hashing on Multi-GPU Nodes
2018
Hash maps are among the most versatile data structures in computer science because of their compact data layout and expected constant time complexity for insertion and querying. However, associated memory access patterns during the probing phase are highly irregular resulting in strongly memory-bound implementations. Massively parallel accelerators such as CUDA-enabled GPUs may overcome this limitation by virtue of their fast video memory featuring almost one TB/s bandwidth in comparison to main memory modules of state-of-the-art CPUs with less than 100 GB/s. Unfortunately, the size of hash maps supported by existing single-GPU hashing implementations is restricted by the limited amount of …
An effective extension of the applicability of alignment-free biological sequence comparison algorithms with Hadoop
2016
Alignment-free methods are one of the mainstays of biological sequence comparison, i.e., the assessment of how similar two biological sequences are to each other, a fundamental and routine task in computational biology and bioinformatics. They have gained popularity since, even on standard desktop machines, they are faster than methods based on alignments. However, with the advent of Next-Generation Sequencing Technologies, datasets whose size, i.e., number of sequences and their total length, is a challenge to the execution of alignment-free methods on those standard machines are quite common. Here, we propose the first paradigm for the computation of k-mer-based alignment-free methods for…
An FPGA aligner for short read mapping
2012
The rapid growth of short read datasets poses a new challenge to the mapping of short reads to a reference genome in terms of sensitivity and execution speed. In this work, we present a parallel architecture for short read mapping utilizing field programmable gate array (FPGA)-based hardware. The computation intensive semi-global alignment and the hash table lookup operations are mapped onto an FPGA. The proposed Align Core is implemented with a parallel block structure to gain computational efficiency. We present a new parallel block-wise alignment structure to approximate the conventional dynamic programming algorithm. The performance of our FPGA aligner is compared to the GASSST and BWA …
An efficient adaptive strategy for searching in peer-to-peer networks
2005
One of the main technical challenges in Peer-to-Peer (P2P) networks is how to efficiently locate desired resources. Although structured systems, based on distributed hash tables, can achieve fair effectiveness, they are not suitable for widely deployed Internet applications. In fact, this kind of systems shows many severe limitations, such as ignoring the autonomous nature of peers, and supporting only weakly semantic functions. Unstructured P2P networks are more attractive for real applications, since they can avoid both the limitations of centralized systems, and the drawbacks of structured approaches. However, their search algorithms are usually based on inefficient flooding schemes, tha…
DSMAV: An improved solution for multi-attribute search based on load capacities
2016
DHT (Distributed Hash Table) such as CHORD or PARTRY facilitates information searching in scalable systems. Two popular DHT-based approaches for range or multi-attribute search are to rely on attribute-value tree and a combination of attributes and values. However, tradeoff between a load balancing mechanism and query efficiency is a challenging task for such information searching systems. In this paper, we propose improved algorithms for a system called DSMAV in which information resources are distributed fairly among nodes and found based on multi-attribute queries in a small number of hop counts. Our system creates identifiers from resource names, each of which is a combination of attrib…
WarpCore: A Library for fast Hash Tables on GPUs
2020
Hash tables are ubiquitous. Properties such as an amortized constant time complexity for insertion and querying as well as a compact memory layout make them versatile associative data structures with manifold applications. The rapidly growing amount of data emerging in many fields motivated the need for accelerated hash tables designed for modern parallel architectures. In this work, we exploit the fast memory interface of modern GPUs together with a parallel hashing scheme tailored to improve global memory access patterns, to design WarpCore -- a versatile library of hash table data structures. Unique device-sided operations allow for building high performance data processing pipelines ent…
MetaCache-GPU: Ultra-Fast Metagenomic Classification
2021
The cost of DNA sequencing has dropped exponentially over the past decade, making genomic data accessible to a growing number of scientists. In bioinformatics, localization of short DNA sequences (reads) within large genomic sequences is commonly facilitated by constructing index data structures which allow for efficient querying of substrings. Recent metagenomic classification pipelines annotate reads with taxonomic labels by analyzing their $k$-mer histograms with respect to a reference genome database. CPU-based index construction is often performed in a preprocessing phase due to the relatively high cost of building irregular data structures such as hash maps. However, the rapidly growi…
A secure architecture for P2PSIP-based communication systems
2009
Today, Peer-to-Peer SIP based communication systems have attracted much attention from both academia and industry. The decentralized nature of P2P might provide the distributed peer-to-peer communication system without help of the traditional SIP server. However, it comes to the cost of reduced manageability and therefore causes security problems, e.g. distrust, privacy leaks, unpredictable availability, etc. In this paper, we investigate on P2PSIP security issues and propose a proxy-based system architecture that improves security during P2PSIP session initiation. The main issues considered in this architecture include Source inter-working, Encryption & Decryption, Policy Management, Desti…
Algorithmic Complexity Vulnerability Analysis of a Stateful Firewall
2016
Algorithmic complexity vulnerabilities are an opportunity for an ad-versary to conduct a sophisticated kind of attack i.e. on network infrastructure services. Such attacks take advantage of worst case time or space complexity of algorithms implemented on devices in their software. In this paper we address potential risks introduced by such algorithmic behavior in computer networks in particular on a stateful firewall. First we introduce the idea and theoretical background for the attack. We then describe in full detail a successfully con-ducted attack which takes advantage of the worst case computational complexi-ty of O(n2) of a hash table data structure used to store active sessions. The …
Trust enhancement of P2PSIP communication systems
2011
Today, peer-to-peer (P2P) session initiation protocol (SIP)-based communication systems have attracted much attention from both academia and industry. The decentralised nature of P2P might provide the distributed P2P communication system without help of the traditional SIP server. However, it comes to the cost of reduced trustworthiness and may cause security problems, e.g., privacy leaks, unpredictable availability, etc. In this paper, we investigate P2PSIP security issues and propose a subjective logic-based trust model that offers trust-based security services during P2PSIP session establishment. The main issues considered in this model include opinion calculation, opinion maintenance, d…